/*

http://codekata.pragprog.com/2007/01/kata_two_karate.html

Alberto Massa
11th of April, 2010

prima volta - due ore, non ci ho tirato fuori nulla
seconda volta.

12:30

*/

#include <stdio.h>
#include <math.h>

#include "3test.c"

void printarr(int a[], int l) {
	int i;
	printf("[");
	for(i=0; i<l; i++) {
		printf("%d, ",a[i]);
	}
	printf("]");
}

void main(void) {
	printf("Dicotomic search - karate chop\n");
	printf("third version, recursive slicing array.\n");

	test();

	printf("\n.\n");
}

int *slice(int *in, int begin, int end) {
	int 
	len = end-begin,
	j = 0, i = 0,
	*out;

	out = (int *) malloc(len*sizeof(int));
	for(i=begin; i<end; i++)  {
		out[j++] = in[i];
	}
	printf("\nslice --> ");printarr(out, len);
	return out;
}


int chop(int n, int *in, int inlength) {

	int t;
	
	printf("\n==================== chop");
	if(inlength == 0)return -1;
	if(in[inlength/2]==n) return inlength/2;
	
	t = recursive_chop(n, in, inlength, inlength/2);
	printf("\n=== returned: %d", t);
	return t;
}

/*
x: numero da cercare
a: array su cui fare lo slice
l: lunghezza dell'array
i: indice totale
*/
int recursive_chop(int x, int *a, int len, int i) {
	int j, y;
	int *slicedarray;
	
	printf("\nrecursive_chop x:%d len:%d i:%d\n", x, len, i);
	printarr(a, len);

	if(len<1) {
		printf("\n\n eh???");
		return -1;
	}
	if(len==1) {
		if(x==a[0])return i;
		else return -1; 
	}
	if(len==2) {
		//recursion base: termination condition
		printf("\nsiamo alla terminazione");	
		if(x==a[0]) return i;
		else if(x==a[1]) return i+1;
		     else return -1;	
	}
	else {
		printf("\n");
		j = floor(len/2);
		y = a[j];
		printf("dudey:%d at %d\n", y, j);
		if(y==x) return i+j;
		else {
			if(x>y) {
				printf("\n >");
				slicedarray = slice(a, i, len);
				return recursive_chop(x, slicedarray, len-1, i);
			} else {
				printf("\n <");
				slicedarray = slice(a, 0, i);
				return recursive_chop(x, slicedarray, i, i-len/2); 
			}
		}
	}
}
